/*
 * @lc app=leetcode.cn id=23 lang=swift
 *
 * [23] 合并K个升序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        if lists.count == 0 {
            return nil
        } else if lists.count == 1 {
            return lists[0]
        }
        let center = lists.count / 2
        let left = mergeKLists(Array(lists[0..<center]))
        let right = mergeKLists(Array(lists[center..<lists.count]))
        return mergeTwoLists(left, right)
    }

    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let root = ListNode(0)
        var cursor: ListNode? = root
        var nl1 = l1
        var nl2 = l2
        while nl1 != nil || nl2 != nil {
            guard let newl1 = nl1 else {
                cursor?.next = nl2
                break
            }

            guard let newl2 = nl2 else {
                cursor?.next = nl1
                break
            }

            if newl1.val < newl2.val {
                cursor?.next = nl1
                nl1 = nl1?.next
            } else {
                cursor?.next = nl2
                nl2 = nl2?.next
            }
            cursor = cursor?.next
        }

        return root.next
    }
}
// @lc code=end

